COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00033 ENDMK
C⊗;


Abstract

     SRI proposes a program of research and development with the goal
of helping to satisfy the needs of the AI and computer science
research communities for support of LISP in the 80's.  Our proposed
program has both technical and administrative components.
   
     The technical plan encompasses the concurrent development of a
VAX NIL implementation and a portable INTERLISP implementation, with
the VAX as the first target machine.  These two efforts will be
strongly coupled, and will share code to the maximal degree possible.
The NIL project will use as a starting point the results of a current
public-domain effort at MIT.  Its main emphasis will be on the
completion of a production version of this system that can be put into
general use as expeditiously as possible.  The portable INTERLISP
component will continue an effort begun under NAVELEX and SRI
sponsorship, and will emphasize research into and development of a
portability concept that will ultimately be applicable to arbitrary
LISP dialects.
     
     The administrative aspect of the proposed program will address a
number of non-technical, but nevertheless critical, aspects of the
language support problem.  First, a cooperative arrangement will be
organized among implementers of the generic MACLISP dialects of LISP
with the goal of promoting compatibility and stability.  As part of
this arrangement the S-1 NIL, VAX NIL, and SPICELISP dialects will be
standardized.  Second, an appropriate steering committee (or two
committees with some overlapping membership) will be established.  This
would be helpful in facilitating a more formal cooperation among those
working on different generic MACLISP dialects, in overseeing the
INTERLISP effort, and in providing a formal basis for interaction
between the MACLISP and INTERLISP communities.  Finally, a group of
people will be assembled at SRI for the specific purpose of providing
maintenance, documentation, and other services for the users of the
products developed in this program.


Introduction

     For the past decade the LISP language has served as the mainstay
of AI and other computer science research in this country.  The
ubiquity and stability of the DEC-10 as a research vehicle made it
possible to share LISPs and LISP-based tools in a manner never before
experienced in the 25-year history of the language.  As the 70's
progressed, however, it became clear that this stability would not
last forever.  First, programs quickly grew sufficiently large to
stress the meager (by today's standards) bounds of the 18-bit virtual
address space.  Second, dramatic advances in LSI fabrication
technology, and dynamic memory technology in particular, made it
possible to begin thinking about personal computers as serious
contenders for the research capital equipment dollar.

     The problem of insufficient address-space headroom was recognized
as early as 1974 with the addition of overlay features for compiled code
in INTERLISP-10.  As the decade unfolded, it became clear that such
measures represented at best a stop-gap solution to the address space
problem.  In the late 70's, researchers developing large systems began
spending intolerably great fractions of their time to circumvent space
limitations.

     The 70's also gave rise, for the first time, to the possibility
of placing LISP in a personal computer setting.  The LISP MACHINE
project spearheaded by Greenblatt and Knight at MIT was among the
first steps in this direction.  The Alto BYTELISP project originated
by Deutsch at Xerox around 1973 soon became the first transportable
LISP architecture for personal computers.  At present, at least half a
dozen personal machines that can support LISP are either available or
in various stages of development.

     As the 80's unfold, it is clear that the era of the DEC-10 is
nearly over and that less expensive time-shared machines (such as the
VAX) and the new generations of personal machines are destined to
become the new workhorses.  It seems equally clear, however, that no
single machine architecture is likely to emerge, at least for the
foreseeable future, as a new de facto standard.  The research
community and its sponsors may be faced with the potentially critical
problem of providing language support for a myriad of new machines.
As the present decade progresses, moreover, and as new and more
powerful micro-processors arrive on the scene--each with a shorter
"half-life", perhaps, than its predecessors--the proliferation
problem will sharpen.

    As a first step in seeking solutions to the language support
problem, ARPA organized a discussion forum held at SRI in April 1981
with representation from diverse segments of the computer science
and artificial intelligence research communities.  While many
different and often conflicting points of view were expressed
at that meeting, a number of specific needs were nearly
universally recognized:

(1)  Hardware Resources

     The need for additional hardware to relieve the problems of both
     inadequate address space and inadequate cycles was felt to be 
     critical, even in the short run.

(2)  Continued Language Support

     It was widely held that both the INTERLISP and the MACLISP branches
     of the LISP community would need continuing support.  In particular,
     it was felt that having both of these running on the VAX was crucial
     for the intermediate term.	

(3)  Unification of the MACLISP community

     The MACLISP family of languages is infamous for its instability
     with respect to inter-dialect incompatibilities, documentation,
     and user support in general.  It was felt that a plan for a
     continuing collaboration among implementers of MACLISP dialects
     is needed to reduce incompatibilities and promote sharing.
     It was also agreed that the kind of institutionalization of
     user-support services that INTERLISP has enjoyed is sorely
     needed.  It was felt too that MACLISP would benefit greatly
     from the programming environment facilities that INTERLISP
     provides.

(4)  Research on Portability

     Whatever short-term measures are taken, it was universally
     agreed that research into ways of increasing the longevity
     of language implementations through portability is
     essential.  

     The plan presented in this proposal addresses all but the
first of these needs.  We feel that SRI, by virtue of its own
stake in LISP, and by virtue of the stability that an institution
like SRI can provide, is an ideal setting for the work required
to satisfy these needs.  The following sections describe our
plan in some detail, and outline a time-table that we feel reasonably
approximates what can be accomplished.


Method of Approach

     Our proposed approach has three interdependent components, two
of which are technical and one of which is administrative: the completion
of a production version of the NIL programming language for
VAX-UNIX; the development of a portable INTERLISP environment with
VAX-UNIX as the first target; and the institution of a formal
mechanism for cooperation both within the separate MACLISP and
INTERLISP communities, and between them.

    The emphasis of the NIL component of the project will be on
satisfying the need for an efficient and well-supported LISP from the
MACLISP family on the VAX.  The main emphasis of the portable
INTERLISP component will be to establish a methodology for building
easily-ported implementations of LISP without undue sacrifice of
efficiency.  That effort will, however, produce a production version of
INTERLISP for the VAX.  Owing to the commonality of target machine, it
will be possible to share a good deal of low-level code between the
NIL and INTERLISP components.  The common code will encompass
operating system interfaces and arithmetic packages, and may even
extend to higher levels.  We expect this sharing to expedite the two
components of the project, and also to serve as a basis for bringing
the INTERLISP and MACLISP communities more closely together.

     The administrative component of our proposal has four goals.
First, it will provide for cooperation among the several NIL efforts,
including SPICELISP, S1-NIL, and the VAX effort.  This cooperation
will both standardize the dialect, and permit the sharing of a large
body of software.  Second, a steering committee will be formed to
facilitate a more formal relationship among the member dialects of
the generic MACLISP community.  Similarly, a steering committee for
the INTERLISP dialect will be formed to ensure the continuation of
the harmony that has characterized the various implementations of
that dialect in the past.  Third, a cooperation will be promoted
between the NIL and INTERLISP components of the project to arrange
the sharing of code as much as possible, and to permit the
application of porting techniques developed during the project to
be applied to the NIL effort.  Finally, a group will be organized
at SRI to provide continued maintenance and documentation for the
systems produced by the project.

     The following two sections describe the technical components
of the project in greater detail.

The NIL Implementation

     Briefly, NIL is a New Implementation of LISP of the MACLISP
genre.  Arising out of the need to go beyond the DEC-10 architecture
and to properly utilize the new-generation stock hardware on the
market, it is a congenial extension of MACLISP, with a few minor
incompatible changes to account for basic language corrections
which could not be easily retrofit.

     NIL is intended to be highly machine independent, and thus not
tied to the particular architectural features of a special-purpose
machine, such as the MIT LISP Machine.  Moreover, it expects to take
advantage of a large virtual-address space, and of the features common
to stock computers generally available to the AI and computer science
communities.  An effort has been under way at MIT for several years
towards this end; a first "native version" is presently coming up on a
VAX 11/780 running the VMS operating system. 

      The implementation effort we propose will build upon the MIT
product, which is in the public domain.  A preliminary version of this
product should be available to selected sites in June 1981.  In
addition, certain parts of the S-1 NIL project carried out during the
summer of 1981, and of the SPICE project at CMU are expected to be
incorporable.

    The major goals of the implementation are as follows:

(1) To be maximally upward compatible with MACLISP.  We expect to
     absorb enough of the LISP Machine's facilities so as to enable most
     non-system programmers to run their applications in either 
     environment.  (In particular, the non-I/O oriented parts of programs
     should be compatible with trivial effort on the programmer's part.)

(2) To provide a rich set of primitive data types, which will reflect
    capabilities of typical off-the-shelf computers, and also to
    provide a general user-extensible mechanism for new data types
    (going beyond the capabilities of ECL, for example.)

(3) To build NIL in NIL, not merely as a curiosity, but to demonstrate
    the feasibility of building an environment in NIL itself, and
    to make it easier for the end-user of LISP to tailor the system to
    personal requirements.  The non-LISP kernel corresponds roughly
    to the microcode complement in a special-purpose LISP machine.
    
(4) To provide EMACS and MACSYMA in NIL.  A very usable EMACS has been
    built under the Multics MACLISP, but suffers from an efficiency
    problem and a proprietary interest limitation (by Honeywell).
    MACSYMA has already begun the slow process of abstracting much
    of the old code during its rebuilding under Multics MacLISP and
    the LISP Machine.  The overall performance of NIL must be high
    enough so that these systems can be competetively supported.

(5) To provide "object-oriented" programming as an adjunct to
    standard LISP recursion style.  Message passing semantics
    has been seen as the appropriate way to think about certain problems,
    but we feel that it is not a panacea, and thus its provision
    in NIL will not ubiquitously displace standard LISP capabilities.

(6) To provide a peak-performance compiler, with modes of "partial
    compilation."  For example, in one mode, the output is truly
    machine-independent code called LLCODE (for Linearized LISP
    code).  Generation of actual machine code instructions from 
    LLCODE permits a number of compile-time choices.

     A more complete discussion of goals and a report on the
current status of NIL are given in an appendix.


Portable INTERLISP

As new generations of machines become available, we believe that the
most sensible approach to the control of LISP support costs is to
promote portability as much as possible.  If we are to take full
advantage of the state of the art in hardware technology as it
evolves, we have no other choice but to increase the durability and
hence longevity of our software investments.  To a certain extent, of
course, we have been exploiting portablity all along.  The large body
of code that lies above the Interlisp Virtual Machine interface, for
example, is largely (though not perfectly)
common to all of the
existing INTERLISP implementations.  As new hardware alternatives
become more concentrated in time, however, and especially as the new
generations of non-microcodable microprocessors become attractive
implementation targets, it will be necessary to place greater emphasis
on portable LISP architectures.

     An effort to develop a methodology for a portable but efficient
INTERLISP implementation was begun in the SRI Computer Science
Laboratory under Navelex and SRI sponsorship in 1980.  The methodology
is based on a low-level virtual machine concept that was first
introduced by J. Chailloux (a member of the proposed project team) for
the purpose of porting implementations of the VLISP dialect.  VLISP is
a work-horse dialect for serious computer science research in Europe.
It apparently runs on more machines, large and small, than any other
single dialect of LISP.  Among these are the DEC-10 and 20 (under
TOPS-10, TOPS-20, WAITS, IRCAM, and TENEX), the DEC-11 (under RT11 and
RSX11), the TI1600(BDOS/D), the SOLAR 16 (TSF), the TRS-80 (TRS-DOS)
(in simplified form), and the 8080.  A Motorola 68000 version is
currently approaching completion.

     The virtual machine concept is somewhat akin to Deutsch's
ByteLISP idea [  ], but is conceptually cleaner and is not at
all dependent on microcode support.  In view of the desirability
of porting to microprocessors, this last feature is extremely
important.  The VLISP experience has shown that the effort
required to bring this virtual machine to new targets is on the
order of man-months rather than man-years.  This experience
has also shown that performance need not be significantly
sacrificed in trade for portability.  Timing tests, for example,
conducted at SRI pitting interpreted VLISP against interpreted
INTERLISP on the KL under TOPS-20 show VLISP running nearly
an order of magnitude faster.  More remarkable, considering
the reputation of the DEC-10 implementation of INTERLISP for
poor interpreter performance, is a test comparing interpreted
MACLISP on the F2, INTERLISP on the F2, and VLISP running on
the Radio Shack TRS-80.  The test, using a standard coding
of the Fibonnaci function, was designed to measure function
calling response, which accounts for a large part of LISP's
performance.  The results showed VLISP running somewhat
faster than MACLISP and nearly one and a half times faster
than INTERLISP.  It should be noted, incidentally, that the
tail-recursion feature of VLISP was not used in these tests.

     The results of any timing tests comparing different
dialects and/or implementations on a small number of
benchmarks must, of course, be interpreted with great caution.
We believe, however, that these tests adequately demonstrate
that further investigation of the virtual machine concept used
is worthwhile.

     The Navelex effort produced a compiler written in
INTERLISP for compiling virtual-machine instructions into
INTERLISP LAP as a development tool.  We propose to continue
that effort with the goal of learning more about portable
LISP implementation in general, and producing a portable
INTERLISP implementation in particular.

     The choice of the VAX as a first target machine will 
permit sharing code with the NIL component of the effort, and
will also serve to back up the current INTERLISP implementation
project at ISI.  The product resulting from the effort will be
transportable to a variety of architectures supporting large
address spaces, including both microcoded machines (such as the
F5 and PERQ) and microprocessor-based machines (such as the
Apollo and machines based on the INTEL 432 and the National 16000).


Statement of Work


First Year
	
   Common Tasks

     *  Identify and develop the kernel common to NIL and
        portable INTERLISP implementations:

           - VMS Operating System Interface
           - Arithmetic Package
           - LLCODE

     *  Investigate possibilities for sharing at higher levels
     *  Organize steering committees for INTERLISP and generic MACLISP

   NIL Tasks

     *  Standardize SPICELISP, S-1 NIL, and VAX NIL where possible
     *  Purify the NIL sources
     *  Develop a user manual (to be updated semiannually)
     *  Develop a primitive user environment
     *  Release a production version for evaluation by user community

   INTERLISP Tasks

     *  Complete the virtual machine definition (including virtual 
        operating system interface)
     *  Complete the design of the interpreter and begin implementation in
        virtual machine code
     *  Purify the INTERLISP virtual-machine sources
     *  Begin compiler development


Second Year

   Common Tasks

     *  Port the kernel to the UNIX environment
     *  Continue development of shared code, where appropriate

   NIL Tasks

     *  Improve the compiler
     *  Adapt the system to UNIX
     *  Begin development of INTERLISP-like facilities
     *  Updates to documentation
     *  Release second production version

   INTERLISP Tasks
  
     *  Begin implementation of virtual machine on VAX
     *  Complete coding of interpreter
     *  Continue compiler development


Third Year

   Common Tasks

     *  Develop plan for continued maintenance and user support
        for both systems

   NIL Tasks

     *  Tune the system further
     *  Update the documentation
     *  Enrich the environment, including EMACS and
        INTERLISP-like debugging facilities
     
   INTERLISP Tasks

     *  Complete the compiler
     *  Complete documentation
     *  Release the production version of the system
     *  Evaluate and tune